/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    int gCounter;
    vector<vector<TreeNode *> > f;
    TreeNode * clone(TreeNode *root) {
        if (root==NULL) return NULL;
        TreeNode *ret=new TreeNode(root->val);
        ret->left=clone(root->left);
        ret->right=clone(root->right);
        return ret;
    }
    void fillTree(TreeNode *root) {
        if (root==NULL) return;
        fillTree(root->left);
        root->val=gCounter;
        ++gCounter;
        fillTree(root->right);
    }
public:
    vector<TreeNode *> generateTrees(int n) {
        if (f.size()<2) {
            f.push_back(vector<TreeNode *>());
            f[0].push_back(NULL);
            f.push_back(vector<TreeNode *>());
            f[1].push_back(new TreeNode(1));
        }
        for (int i=f.size();i<=n;i++) {
            vector<TreeNode *> tmp;
            for (int j=0;j<=i-1;j++)
                for (int p=0;p<f[j].size();p++)
                    for (int q=0;q<f[i-1-j].size();q++) {
                        TreeNode guard(0), *guardClone;
                        guard.left=f[j][p];
                        guard.right=f[i-1-j][q];
                        guardClone=clone(&guard);
                        gCounter=1;
                        fillTree(guardClone);
                        tmp.push_back(guardClone);
                    }
            f.push_back(tmp);
        }
        return f[n];
    }
};
